#include"Heap.h"

void HeapInit(Heap* hp)
{
    assert(hp);
    hp->a = NULL;
    hp->size = hp->capacity = 0;
}



void HeapCreate(Heap* hp, HPDataType* a, int n)
{
    assert(hp);
    if (hp->capacity == hp->size)
    {
        int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(hp->a,newcapacity * sizeof(HPDataType));
        if (tmp == NULL)
        {
            printf("realloc fail");
            exit(-1);
        }
        hp->a = tmp;
        hp->capacity = newcapacity;
    }
    hp->a[hp->size] = n;
    hp->size++;
}



void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->a);
    hp->a = NULL;
    hp->size = hp->capacity = 0;
}



void Swap(HPDataType* parent, HPDataType* child)
{
    int tmp = *parent;
    *parent = *child;
    *child = tmp;
}

void AdjustUp(HPDataType* a, HPDataType child)
{
    int parent = (child - 1) / 2;
    while (child>0)
    {
        if (a[parent] > a[child])
        {
            Swap(&a[parent], &a[child]);
            parent = (parent - 1) / 2;
            child = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}


void HeapPush(Heap* hp, HPDataType x)
{
    assert(hp);
    HeapCreate(hp,hp->a,x);
    AdjustUp(hp->a,hp->size-1);
}




void AdjustDown(HPDataType* a,int size,int parent)
{
    int child = parent * 2 + 1;
    while (child<size)
    {
        if (child + 1 < size && a[child] > a[child + 1])
        {
            child = child + 1;
        }

        if (a[parent] > a[child])
        {
            Swap(&a[parent], &a[child]);
            parent = parent * 2 + 1;
            child = child * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapPop(Heap* hp)
{
    assert(hp);
    assert(hp->size>0);

    Swap(&hp->a[0], &hp->a[hp->size - 1]);
    hp->size--;

    AdjustDown(hp->a,hp->size,0);
}



HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    assert(hp->size > 0);
    return hp->a[0];
}



int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->size;
}



int HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->size == 0;
}